package leetcode.editor.cn;

import java.util.Stack;

class AddTwoNumbersIi {
    public static void main(String[] args) {
        Solution solution = new AddTwoNumbersIi().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        // https://leetcode.cn/problems/add-two-numbers-ii/solution/liang-shu-xiang-jia-ii-by-leetcode-solution/
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            // 使用栈保存结果
            Stack<Integer> stack1 = new Stack<>();
            Stack<Integer> stack2 = new Stack<>();
            ListNode cur1 = l1, cur2 = l2;
            while (cur1 != null) {
                stack1.push(cur1.val);
                cur1 = cur1.next;
            }

            while (cur2 != null) {
                stack2.push(cur2.val);
                cur2 = cur2.next;
            }

            ListNode pre = null;
            int temp = 0;   // 进位
            // [5] [5] 的情况是10
            while (!stack1.isEmpty() || !stack2.isEmpty() || temp != 0) {
                int val1 = stack1.isEmpty() ? 0 : stack1.pop();
                int val2 = stack2.isEmpty() ? 0 : stack2.pop();

                int sum = val1 + val2 + temp;
                temp = sum / 10;

                // 注意是逆序
                ListNode cur = new ListNode(sum % 10);
                cur.next = pre;
                pre = cur;
            }

            return pre;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
